1. Field of the Invention
This invention relates to a method and apparatus for allocating and freeing storage in an information handling system and, more particularly, to a method and apparatus lor allocating and freeing storage utilizing multiple tiers of storage organization.
2. Description of the Related Art
In the C programming language, applications use the function malloc() to allocate a piece of storage, the function free() to release the storage for subsequent reuse, and the function realloc() to change the size of a piece of storage. (The double parentheses are standard notation for C library calls.) These functions, which are sometimes referred to as heap management, are well known in the art and are described in any of a number of references on the C programming language and its extensions.
There is a generally accepted heap manager that is used on many UNIX.RTM. systems. This algorithm, known as the Stephenson algorithm after its inventor, obtains storage in the size requested and uses a binary tree to keep track of free elements. The algorithm works relatively well in a single-threaded process where there is only one caller in malloc() or free() at a given time. The problem occurs when running many threads in a single process. When these threads call malloc() and free(), it is necessary for the heap manager to obtain serialization to control updates to the binary tree. This serialization causes contention in the algorithm. When running on a multiprocessor, this serialization causes the multiple threads to stack up on the heap latch and reduces the degree of concurrency that can be achieved. The suspend and resume which occur around the heap latch contention also contribute to significantly longer path length on malloc() and free() requests.
An object of the present invention is therefore to provide high-performance malloc(), free() and realloc() functions which do not create contention in a multithreaded application.